package cn.sjtu.algorithm.prefix_sum;

/**
 * @author syo 2319615164@qq.com
 * @description 二维前缀和
 * @date 2024/5/16
 * @Copyright syo
 */
public class TwoDimensionalPrefixSum {
    public static void main(String[] args) {
        // 将元素以（1，1）开始
        int[][] nums = {{0, 0, 0, 0}, {0, 1, 2, 3}, {0, 4, 5, 6}, {0, 7, 8, 9}};

        int[][] prefixSum = new int[nums.length][nums[0].length];
        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j < nums[0].length; j++) {
                prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + nums[i][j];
            }
        }
        System.out.println(getSum(prefixSum, 1, 1, 2, 2));
    }

    public static int getSum(int[][] prefixSum, int i, int j, int ii, int jj){
      return prefixSum[ii][jj] - prefixSum[i - 1][jj] - prefixSum[ii][j - 1] + prefixSum[i - 1][j - 1];
    }
}
